package org.ayachinene.leetcode.problems;

public class P1824 {

    static class Solution {

        public int minSideJumps(int[] obstacles) {
            int n = obstacles.length - 1;
            // dp[i][j]: 从点i的j跑道出发到点n的最少侧跳次数
            int[][] dp = new int[n + 1][4];
            dp[n][1] = 0; dp[n][2] = 0; dp[n][3] = 0;
            for (int i = n - 1; i >= 0; --i) {
                for (int j = 1; j <= 3; ++j) {
                    dp[i][j] = Integer.MAX_VALUE;
                    // pos(i, j)处有障碍物，不可达。不可能从该位置到达点n
                    if (j == obstacles[i]) {
                        continue;
                    }
                    // k: 从pos(i, j)跳到pos(i, k)
                    for (int k = 1; k <= 3; ++k) {
                        // 要侧跳到的位置有障碍，不可达
                        if (k == obstacles[i]) {
                            continue;
                        }
                        // 跑道相同，无需侧跳
                        if (k == j) {
                            dp[i][j] = Math.min(dp[i][j], dp[i + 1][k]);
                        } else {
                            // pos(i, k)前方有障碍，为了防止溢出，直接跳过
                            if (k == obstacles[i + 1]) {
                                continue;
                            }
                            dp[i][j] = Math.min(dp[i][j], dp[i + 1][k] + 1);
                        }
                    }
                }
            }
            return dp[0][2];
        }
    }
}
